package com.df.sort;

/**
 * 选择排序
 *
 * @author dongfang
 */
public class Select {

    /**
     * <EM>选择排序(Selection sort)</EM>是一种简单直观的排序算法。<BR/>
     * 它的工作原理如下。<BR/>
     * 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
     * <BR/>
     * 选择排序无论初始状态如何,时间复杂度永远是O(n^2),但是移动的数据是最少的;<BR/>
     * 对于长度为N的数组，选择排序需要大约(N^2)/2次比较和N次交换
     *
     * @param array
     */
    public static void select(int[] array) {
        int num = 1;
        int length = array.length;

        int min = 0; // 最小数值下标值
        int temp = 0;

        for (int i = 0; i < length; i++) {
            min = i;
            for (int j = i + 1; j < length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                    num++;
                    // System.out.println("[" + num++ + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                }
            }

            if (min > i) {
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }

        System.out.println("select num [" + num + "]");

    }
}
